• Tree-structured Models (a.k.a. Decision Tree)
  • CART
    
  • GUIDE
  • PARTY
    
  • Extentions of Decesion Tree: Subgroup Identification
    
  • Case Studies using R
• Random Forests
  • Bremen’s Random Forests
    
  • Random forests with conditional inference
    
  • GUIDE Forests (options)
  • Extensions
    
  • Case Studies using R

• Trees as a nonparametric models
  • Trees as a K-NN
  • Trees as an additive model
    
  • Trees as a neural networks

• Neural random forests

• Deep neural decision forests

A decision tree is a logical model represented as a tree that shows how the value of a target variable can be predicted by using the values of a set of predictor (input) variables.

A decision tree recursively partitions the data and sample space to construct the predictive model.

Its name derives from the practice of displaying the partitions as a decision tree, from which the roles of the predictor variables may be inferred.

A classification or regression tree is a prediction model that can be represented as a decision tree.

A tree-structured classifier is a decision tree for predicting a class variable from one or more predictor variables.

A regression tree model is a nonparametric estimate of a regression function constructed by recursively partitioning a data set with the values of its predictor variables.

Recursive partitioning methods have become popular and widely used tools for nonparametric regression and classification in many scientific fields.

An empirical tree represents a segmentation of the data that is created by applying a series of split rules. Each split rule assigns an observation to a segment based on the values of inputs.

One rule is applied after another, resulting in a hierarchy of segments within segments. The hierarchy is called a tree, and each segment is called a node.

The original segment contains the entire data set and is called the root node of the tree. A node with all its successors forms a branch of the node that created it.

The nodes that have child nodes are called interior (or internal, intermediate) nodes. The final nodes that do not have child nodes are called leaves (or terminal nodes). For each leaf, a decision is made and applied to all observations in the leaf.

The type of decision depends on the context. In predictive modeling, the decision is simply the predicted value.

• Splitting recursively
  • Partition the data and sample space recursively to construct a predictive model.
  • Split selection: split variable selection and split set selection
• Determining a tree size
  • Partitioning continues until stopping criteria are met. (Stopping criteria: sample size, impurity, improvement, and so on)
  • Partitioning continues until node sample sizes are too small, and then prune insignificant nodes that cause over-fitting.
• Interpretation and Prediction
  • Interpret the final predictive tree model with the significant split variables.
  • Predict target values of new data using the final predictive tree model.

• Split rule: consisting of a split variable and a split point (or set).
  • \(X \leq c\) for ordered variable
  • \(X \in A\) for unordered variable

• Split rule: determined by examining all possible splits (exhaustive search) or performing statistical tests

• Good split rule: the data being homogeneous within each subnode and heterogeneous between subnodes.

• Naïve stopping rule: Stop splitting if
  • a node sample size is small,
  • a node impurity is low,
  • or an improvement is minor.
• Pruning rule:
  • Step 1: Stop splitting if a node sample size is small.
  • Step 2: Prune off unnecessary branches.

• Loh, W.-Y. (2008). Regression by parts: Fitting visually interpretable models with GUIDE. In Handbook of Data Visualization, C.Chen, W.Härdle, and A.Unwin, Eds. Springer, pp.447-469.

• Loh, W.-Y. (2008). Classification and regression tree methods. In Encyclopedia of Statistics in Quality and Reliability, F.Ruggeri, R.Kenett, and F.W. Faltin, Eds. Wiley, Chichester, UK, pp.315-323.

• Loh, W.-Y. (2010). Tree-structured classifiers. Wiley Interdisciplinary Reviews: Computational Statistics, 2, 364-369.

• Loh, W.-Y. (2011). Classification and regression trees. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 14-23.

• Loh, W.-Y. (2014). Fifty years of classification and regression trees (with discussion). International Statistical Review.

• Merkle, E.C. and Shaffer, V.A. (2011). Binary recursive partitioning: Background, methods, and application to psychology, British Journal of Mathematical and Statistical Psychology, 64, 161–181.

• Morgan, J. N. and Sonquist, J. A. (1963). Problems in the analysis of survey data, and a proposal. J. Amer. Statist. Assoc. 58 415–434.

• Strobl, C., Malley, J. and Tutz, G. (2009). An Introduction to Recursive Partitioning: Rationale, Application, and Characteristics of Classification and Regression Trees, Bagging, and Random forests. Psychological Methods, 14(4), 323–348.

• Piecewise constant least squares models: AID (Morgan and Sonquist, 1964), CART, RPART, GUIDE (Loh, 2002)

• Piecewise linear least squares, polynomial regression, quantile regression, and longitudinal and multi-responses data effects: Loh (2014) with discussion

• Subgroup identification of differential treatment effects: Loh et al. (2014), Hothorn et al. (2014)

• Others: M5 (Quinlan, 1992), MOB (Zeileis et al., 2008), MELT (Eo and Cho, 2014), KAPS (Eo et al., 2015)

• Missing values, selection bias, accuracy, speed, and tree complexity

• Diagnostic tool: Simonoff (2013)

• \(t\) and \(T\): a node and a tree
• \(N\) and \(N(t)\): sample size and number of samples in t
• \(Y\) : response variable
• \(p\): number of predictor variables
• \(k\): number of partitioning variables
• \(X = (X_1, \ldots ,X_p)\): vector of fitted variables
• \(Z = (Z_1, \ldots ,Z_k)\): vector of split variables

1. Fit a constant, the node mean \(\bar{Y}_t\) at a node \(t\)

2. Use sum of squared deviations \(\sum_{i \in t} (Y_i - \bar{Y}_t)^2\) as a node impurity \(i(t)\)

3. Choose the split set that maximizes the decrease in node impurity

4. Use \(\bar{Y}_t\) in node \(t\) as predicted value.

5. Prune tree using test sample or cross-validation

6. Use surrogate spilts to deal with missing values

A naive approach is to evaluate the reduction of impurity, \(\Delta i(\cdot)\), over all possible splits, and select the split set with the greatest reduction of impurity,

1. Define the doofness of a split \(s\) as

\[ \Delta i(s,t) = i(t) - p_L i(t_L) - p_R i(t_R), \]

• where \(t_L\) and \(t_R\) are the left and right subnodes of \(t\) and \(p_L\) and \(p_R\) are the probabilities being in those subnodes.

1. Define a set \(S\) of binary splits of the form \(X \in A\), where,

\[ A = (-\infty, c], \mbox{if $X$ is ordinal} \]

\[ A \in X, \mbox{if $X$ is categorical} \]

• If \(X\) is ordinal (numerical) with \(k\) unique values, there are \((k-1)\) splits
  
• If \(X\) is categorical with \(k\) unique values, there are \((2^{k-1} - 1)\) splits

• Enable tree construction when there are missing values in the learning sample

• Enable classification of new cases with missing values

• Rank variables by their order of importance (not available in rpart)

• Detect masking of variables

• Biased toward variables with more splits
  • A \(k\)-valued ordered variable has \((k − 1)\) splits.
  • A \(k\)-valued categorical variable has \((2^{k−1} − 1)\) splits.
• Biased toward predictors with more missing values
  • Split method uses only proportions of nonmissing cases; it ignores the number of missing values.
  • A variable taking a unique value for exactly one case in each class and missing on all other cases yields the largest decrease in impurity. Bias exists for surrogate splits too.
• Computation
  • Impractical when there are three or more classes and categorical variables with many values. + Note: Because CART and RPART encode each categorical variable split with a 32-bit binary integer, they do not properly deal with categorical variables having more than 32 values.
• Prediction accuracy
  • Often no better than linear discriminant analysis.

For more details, See the talk slide.

See the JCGS paper

At each node, a case goes to the left child node if stated condition is satisfied. Sample sizes are beside terminal nodes.
95% bootstrap intervals for relative risk of treatment vs. placebo below nodes.

Identifying groups of patients for whom the treatment has a different effect than for others. Effect is:

– Stronger
– Lower
– Contrary

than the average treatment effect.

Suitable models promise better prediction of treatment effect and thus individualised treatments.

• subgroups are defined by terminal nodes of a tree.

• Use Piecewise-Linear Models
  • Use Poisson regression to fit a proportional hazards model to each node

• Examine residual patterns for each treatment level

• Why group ordinal variables?
  • Grouping values of ordinal X variables may result in power loss
  • But grouping allows missing values to be used!

• Test for treatment interaction

• Perturb population instead of dat

• The idea discussed here is a simple one that has (perhaps) been underutilized through the years: since the errors are supposed to be unstructured if the model assumptions hold, examining the residuals using a method that looks for unspecified structure can be used to identify model violations. A natural method for this is a regression tree.

• Miller (1996) proposed using a CART regression tree for this purpose in the context of identifying unmodeled nonlinearity in linear least squares regression, terming it a diagnostic tree

• Su, Tsai, and Wang (2009) altered this idea slightly by simultaneously including both linear and tree-based terms in one model, terming it an augmented tree, assessing whether the tree-based terms are deemed necessary in the joint model. They also note that building a diagnostic tree using squared residuals as a response can be used to test for heteroscedasticity.

• The diagnostic trees are not meant to replace examination of residuals or more focused (and powerful) tests of specific model violations; rather, they are an omnibus tool to add to the data analyst’s toolkit to try to help identify unspecified mixed effects model violations.

RE-EM Tree algorithm with diagnostic tools for longitudinal and multi-responses data

• Fit the linear mixed effects model.
• Fit a RE-EM tree to the residuals from this model to explore nonlinearity.
• Fit a RE-EM tree to the absolute residuals from the model to explore heteroscedasticity (squared residuals are more non-Gaussian and lead to poorer performance).

A final tree that splits from the root node rejects the null model.

Even though the growing/pruning rules for the tree are not designed to directly control Type I error, it turns out that they do at a roughly .05 level, resulting in a generally conservative test.

For more details, See the talk slide.

For more details, See Wang's Web

See partykit package in order to build a tree-structured model

tree::tree
rpart::rpart
mvpart::mvpart
party::mob
psychotree:psychotree
betareg::betatree
RWeka::M5
evtree::evtree
REEMtree::REEMtree
vcrpart::vcrpart
kaps::kaps melt::melt

• Goal
  • Predict \(y^{*}\) using learning data \((y,x)_{i=1}^{N}\) \(\rightarrow\) Batch Learning
  • Or, perdict \(y^{*}\) using test data \(x^{*}\) \(\rightarrow\) Online Learning
• Tree-structured Modeling
  • Weak learner
  • Large variance
• Key Idea
  • \(Var(X) = \sigma^2 \rightarrow Var(\frac{1}{n}\sum_{i=1}^{n}X_i) = \frac{\sigma^2}{n}\)
  • with resampling techniques
• Recipe for prediction: Use a random forest
  • Ensemble of randomized decision trees
  • State-of-the-art for lots of real world prediction tasks
  • Do we Need Hundreds of Classifiers to Solve Real World Classification Problems? (Fernandez-Delgado et al., 2014)

• Hierarchical axis-aligned binary partitioning of input space
• Rule for predicting label within each block

• \(T\) : list of nodes, feature-id + location of splits for internal nodes
• \(\theta\): Multinomial parameters at leaf nodes

There are three parameters for RF algorithms:

• \(a_n \in \{1, \ldots, n\}\): the number of sampled data points in each tree
  
• \(mtry \in \{1, \ldots, p\}\): the number of possible directions for splitting at each node of each tree
  
• \(nodesize \in \{1, \ldots, a_n \}\): the number of examples in each cell below which the cell is not split

By default, in the regression mode of the randomForest package, the parameter
mtry = ceiling(p / 3), a_n = n, and nodesize = 5.

RF can be used to rank the importance of variables via two measures of significance:

• Gini importance a.k.a Mean Decrease Impurity (Breiman, 2003a)
  • the total decrease in node impurity from splitting on the variablce, averaged over all trees
  • yielding a high DGI when selected, leading to a high Gini VIM.
• Permutation Importance a.k.a. Mean Decrease Accuracy (Breiman, 2001)
  • if the variable is not important, then rearranging its values shold not degrade prediction accuracy.
  • the difference between the OOB error resulting from a data set obtained through random permutation of the predictor of interest and the OOB error resulting from the original dataset.
  • Increase the OOB error, leading to a high permutation VIM

For more detail, see [Goldstein et al. (2014)].

Set \({\bf X} = (X^{(1)}, \ldots, X^{(p)}).\)
For a forest resulting from the aggregation of \(M\) trees, the MDI of the variable \(X^{(j)}\) is defiend by
\[ \hat{MDI}(X^{(j)}) = \frac{1}{M} \sum_{l = 1}^{M} \sum_{t \in \mathrf{T}_l} p_{n,t} L_{reg, n} (j_{n,t}, z_{n,t}), \] where

For more details, See useR 2008 talk slide.

For more details, See [the JSCS paper].

Online learning is a method in which data becomes available in a sequential order and is used to update our best predictor for future data at each step, as opposed to batch learning techniques which generate the best predictor by learning on the entire training dataset at once

• Yi et al. (2012) propose Information Forests whose construction consists in deferring classification until a measure of classification confidence is sufficiently high, and in fact break down the data so as to maximize this measure.
• Lakshminarayanan et al. (2014) porpose Mondrian Forests which are grown in an online fashion and achieve competitive predicive performance comparable with other online random forests while being faster.
  • Mondrian Forests = Mondrian process + RF
    
  • Mondrian process: a stochastic process over binary hierarchical axis-aligned partitions of \(R^d\) (Roy and Tch, 2009)
  • See Prof. Teh's talk
  • Python package is available at Github

One of the strengths of RF is that they can handle missing data.

RF can naturally be adapted to fit the unbalanced data framework by down-sapling the majority class and growing each tree on a more balanced dataset (Chen et al. 2004; Kuhn and Johnson, 2013).

• Recall that RF is a tree ensemble method. A large number of bootstrap samples are taken from the training data and a separate unpruned tree is crated for each dataset.
• This means that if there are n training set instances, the resulting sample will select n samples with replacement
• To incorporate down-sampling, random forest can take a random sample of size \(c \times nmin\), where c is the number of classes and nmin is the number of samples in the minority class.

Fink et al. (2010) use RF for which each tree is traned and allowed to prediction on a particular region in space and time.

One-class classification (unary classification) tries to identify objects of a specific class amongst all objects, by learning from a training set containing only the objects of that class.

• Define an RF dissimilarity measure between unlabeled data.
  • The idea is to construct an RF predictor that distinguishes the “observed” data from suitably generated synthetic data.
  • A synthetic class outcome is defined by labeling the observed data by class 1 and the synthetic data by class 2. By restricting the resulting labeled similarity measure to the observed data, one can define a similarity measure between unlabeled observations. The similarity measure strongly depends on how the synthetic observations are generated.
  • See Shi and Hovath (2007; JCGS).
• Yan et al. (2013) present a new clustering method called Cluster Forests which randomly probes a high-dimensinoal data cloud to obtain good local clusterings, then aggregates via spectral clustering to obtain cluster assignments for the whole dataset.

For more details, see CRAN Task View

• Defer the decision to generalize beyond the training examples till a new query is encountered
• Whenever we have a new point to classify, we find its K nearest neighbors from the training data.

This shows that the whole forest is again a weighted neighborhood scheme, with weights that average those of the individual trees. The neighbors of x' in this interpretation are the points \(x_{i}\) which fall in the same leaf as x' in at least one tree of the forest. In this way, the neighborhood of x' depends in a complex way on the structure of the trees, and thus on the structure of the training set.

For more detail, See Lin and Jeon (2006).

• Stochastic & differentiable RF
• Unifies representation learning and classifier
• Moves away from greedy, local construction of traditional RFs
• Learning of split node parameters using SGD & backprop
• Given state of tree/network, get leaf predictions

See the talk slide